A number of systems and programs are offered on the market for the design of parts or assemblies of parts, such as the one provided by DASSAULT SYSTEMES under the trademark CATIA. These so-called computer-aided design (CAD) systems allow a user to construct and manipulate complex three dimensional (3D) models of objects or assemblies of objects. CAD systems thus provide a representation of modeled objects using edges or lines, in certain cases with faces. Lines or edges may be represented in various manners, e.g. non-uniform rational B-splines (NURBS). These CAD systems manage parts or assemblies of parts as modeled objects, which are mainly specifications of geometry. In particular, CAD files contain specifications, from which geometry is generated. From geometry, a representation is generated. Specifications, geometry and representation may be stored in a single CAD file or multiple ones. CAD systems include graphic tools for representing the modeled objects to the designers; these tools are dedicated to the display of complex objects—the typical size of a file representing an object in a CAD system extending up to the range of a Mega-byte for part, and an assembly may comprise thousands of parts. A CAD system manages models of objects, which are stored in electronic files.
Designing a mechanical part with a known CAD system amounts to define or modify specification of said part, that is, its geometrical shape and dimensions so that it fits functional and manufacturing requirements. The resulting shape is a combination of basic features: pad, pocket, groove, shaft etc. created by the designer. Through complex geometrical and topological computations, the CAD system yields the boundary representation of the solid (mechanical part) as e.g. a closed and oriented surface. A solid model means a three-dimensional model of an object in a computer.
Designing a modeled object (a part or a product of parts) actually comprises two steps: a conceptual design followed by a detailed design. Conceptual design is to sketch the main shape or skeleton of a 3D object (or assembly of 3D objects) so that it fits a predefined mechanical function. Next step is detailed design, which is to refine the functional shape to take into account manufacturing constraints (forging, casting, welding, sheet metal, electro erosion etc.). Detailed design will however not be further discussed as it is not a main concern for the present invention.
Reverting to conceptual design: since an object is not yet entirely designed at this step, the user deals with simple geometries (mostly profiles including lines and circles, planar faces, cylindrical faces). Furthermore, relative positions of these geometries are modified all along the investigation process. For this purpose, tools are available to change the shape: interactive direct manipulation, positioning and dimensioning constraints. The topology of the object is captured, maintained and updated by the system so that the 3D structure of the object remains consistent. This allows hidden surfaces display, collision detection, mass, area computation, behavior simulation through finite element analysis.
One of the most popular technologies involved in CAD systems is perhaps the “historical design”. Here, the user creates design features via interactive commands and the system captures the ordered sequence of features creation, their input parameters and relationships. So, modifying a solid is for the designer to edit a feature, change its input parameters and for the system to replay the ordered sequence to compute the modified shape.
In contrast, only a few CAD systems are based on the so-called “B-rep modeling” technology. As opposed to historical design, the system here captures only the boundary representation of the solid, although creation tools are very similar to those provided by history-based CAD systems: profiles, extrude, revolute, sweep, round, fillet are such examples. Modifying a solid is performed in two steps. First, the designer selects the portion of the boundary of interest and expresses the change intent (increase round radius value, decrease a hole diameter, remove boss . . . ). Second, the system performs this local change while maintaining the boundary representation closure.
As to boundary representations, it may be distinguished amongst systems which constrain the user to build data representations of real-like objects only, e.g. objects which may actually exist in the real world and systems which allow the user to build data representations of hybrid or impossible objects or data components (such as vertices) that have no physical manifestation. The former are called “manifold modelers”, as opposed to “non-manifold” modeler. Note that non-manifold geometry is often used as intermediate design steps, making it in fact often un-avoidable in true usage of CAD system. The term “manifold” has an exact mathematical definition, which will not be discussed here besides that in 3D, a mathematical manifold corresponds somehow to a physically realizable object.
Next, also known are the recent “functional modeling” systems, which are in fact a layer of software on top of a classical history-based technology.
Besides, it is worth mentioning that all industrial CAD systems provide a 2D sketcher where dimensioning and positioning constraints are available as well as direct manipulation. Some systems provide 2D or 3D dimensioning and positioning constraints at part design level. Nevertheless, only manifold solids can be dimensioned.
In this respect, any industrial CAD system yields a “manifold boundary solid object”, meaning in practice that only thick and regular 3D objects can be modeled. “Regular” means that the boundary of the solid locally cuts neighboring space into exactly two portions (inside and outside), excluding all singularities. “Thick” means that the solid may not locally be approximated by a surface or a wire, meaning that multidimensional objects are out of reach.
Furthermore, most CAD systems provide 3D dimensioning and positioning constraints at assembly level, where solid parts are managed as rigid objects. As a further remark, note that dimensioning and positioning constraints differ from feature parameters, which are often displayed through double arrows and dimension values. A dimensioning and positioning constraint is created a posteriori by the designer and connects arbitrary objects.
As mentioned above, dimension and shape of the mechanical part are controlled by dimensioning and positioning constraints. Dimensioning constraints involve a numerical value (mostly a distance or an angle) through a parameter. Changing the numerical value is for the designer to edit the parameter.
Other features may be used to capture the design intent. These are: design variables, equalities or inequalities, collectively named “engineering equations”. A design variable is set by the designer or by a formula and captures a typical numerical value of importance. An equality is a mathematical function involving design variables, constraints parameters, or topological objects (solid, face, curve) into a single formula targeting zero value: f(a, b, c, . . . )=0, as opposed to an inequality that targets a range of values f (a, b, c, . . . )≧0. The mathematical function is usually evaluated by an algebraic formula, a predefined table or a computer program. Typically, the dimensional parameters of a solid may change while preserving a constant volume V0. This may for instance be captured by adding the equality Volume(Solid)−V0=0 to the set of constraints. Preserving the area of a closed contour or the length of a curve is done the same way. Distance d separating two parallel planes can be controlled by an equation d−2b=0 where b is a design variable. If the overall mass of a solid part must not exceed a given value mmax, the inequality ρVolume(Solid)≦mmax is needed, where ρ is a constant parameter depending on the part material.
For the sake of completeness, fundamentals of traditional solid modeling can be found in “Geometric and solid modeling: an introduction” C. M. Hoffmann, Morgan-Kaufmann 1989. Fundamentals of cell complex applied to geometric modeling can be found in “SGC: a dimension independent model for point sets with internal structures and incomplete boundaries” J. R. Rossignac, M. A. O'Connor, IBM research report RC14340, 1989. Fundamentals of 3D dimension and constraint management can be found in “Solving geometric constraints systems”, G. A. Kramer, M.I.T Press and “A brief on Constraint Solving” C. M. Hoffmann and R. J. Arinyo, Computer-Aided Design and Applications, Vol. 2, No. 5, pp 655-663, 2005.
Next, the following research papers deal with conceptual design by sketching, dragging and deforming solid objects:
“Constraint objects—integrating constraint definition and graphical interaction”, H Hsu, B. D Bruderlin, Solid Modeling '93, Montreal, Canada.
“Inferring 3D models from freehand sketches and constraints”, L. Eggli, H Hsu, B. D Bruderlin, G. Elber, Computer Aided Design, Vol. 29, pp. 101-112, 1997.
“A constraint-based manipulator toolset for editing 3D objects” C. Hsu, G. Alt, Z. Huang, E. Beier, B. Bruderlin, Solid Modeling '97, Atlanta USA.
“A constraint-based shape modeling system” B. Bruderlin, U. Doring, P. Michalik, Geometric constraint solving & applications, Springer Verlag, 1998.
The methods disclosed in the research papers above actually make use of positioning and dimensioning constraints to arrange faces, edges and vertices of solids so that free deformation is possible. The data model captures the whole solid through coincidence constraints. In other words, the topology of the boundary representation is translated into point/plane coincidence constraints. Starting from the object to move (a face or a vertex), this network is traversed to get degrees of freedom (DOF) of geometrical objects. A so called “dependency graph” is computed from the sub-graph resulting from traversal of the network. The dependency graph used to update geometries is an acyclic graph.
Also known is Google's SketchUp software (2007), which allows for creation and direct manipulation of solid models. Snapshots represented on FIGS. 1A-B show that pulling vertex 1 along line 2 breaks planarity of face 3. However, how topological consistency is saved in this case is not suited for today's industrial CAD. In this case, design intent of the user is lost. Furthermore, how the system splits face 3 into two adjacent triangles (as shown in FIG. 1B) is out of the designer's control.
Next, modifying a “history based” solid requires dealing with the complexity of its history. Not all modifications are possible, only those that are compatible with the creation path. This inhibits creativity at conceptual phase, where, by nature, unexpected changes may happen. B-rep modeling systems are more flexible from this point of view, but they do not provide genuine 3D dimensioning and positioning constraints at part level. Constraints can be created in 2D or 3D sketches, while non driving constraints (measuring constraints) are created at part level. Consequently, 3D and easy accurate design is out of reach. In addition, such system cannot support other constraint types, such as kinematics or dynamics constraints, nor engineering equations.
Furthermore, all 3D industrial CAD systems yield a “manifold boundary solid object”. As said, only thick and regular objects can be contemplated, such that multidimensional objects cannot be contemplated. In contrast, non-manifold boundary representation means data which can represent not only a manifold, but also a non-manifold (e.g. one edge shared by more than two faces). Mathematically speaking, the representation space corresponds to a Euclidean Cell Complex.
To illustrate the above concepts, FIGS. 2A-2C illustrate three versions of the same object 5. The leftmost object is the conceptual view: an L-shape part equipped with a stiffener. The main shape is set, but actual thickness is not yet defined. Only a non manifold modeler can support this shape. The middle object combines a thick L-shape solid together with a zero thickness (surface) stiffener. Here, the stiffener thickness is not yet defined. Once more, only a non manifold modeler would support this multi dimensional shape as a mix of a 3D solid and 2D surface. The rightmost object is the traditional manifold representation available in any industrial CAD system. The solid is bounded by a closed and oriented surface.
Besides, known algorithms to deform solids through constraints use a “brute force” solution, which is inoperative. The “brute force solution” is to pickup all geometries and all constraints, translate all topological adjacencies into coincidence constraints, and send this to the solver. This is not convenient and effectively fails for the following reasons.                Firstly, the system is always under-constrained, which means that infinity of solutions exists. Consequently, this raises the risk of unexpected behavior: the designer hardly tolerates that a piece of geometry not involved in the modification is moved by the solver, even if it is correct from the theoretical point of view.        Secondly, the solving performance does not fit real time or even interactive response time, even for a rather small model.        Thirdly, large models saturate the solvers capabilities: either computer time or memory management.        Fourthly, the update complexity is proportional to the complexity of the entire model, and not to the complexity of the modification as expected by the designer.        
Therefore, there is a need for finding a solution for lowering the risk of unexpected behavior, when modifying a modeled object with a CAD system. Furthermore, said solution should result in acceptable response time and be compatible with large models, without saturating solvers capabilities.